/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-03-21
 * Time: 18:07
 */
class Solution {
        public int numDecoding1(String s) {
                int n = s.length();
                char[] str = s.toCharArray();
                //1.状态表示
                int[] dp = new int[n];
                //2.初始化
                if(str[0] != '0') {
                        dp[0] = 1;
                }
                //因为字符串有可能只有一个，处理边界
                if(n == 1) {
                        return dp[0];
                }
                if(str[0] != '0' && str[1] != '0') {
                        dp[1]++;
                }
                int t = 10 * (str[0]-'0') + (str[1]-'0');
                if(t <= 26 && t >= 10) {
                        dp[1]++;
                }
                //3.状态转移方程
                //4.填表顺序
                for(int i = 2; i < n; i++) {
                        //i位置单独编码
                        if(str[i] != '0') {
                                dp[i] += dp[i-1];
                        }
                        //i-1与i一起编码
                        int t1 = 10 * (str[i-1]-'0') + (str[i]-'0');
                        if(t1 <= 26 && t1 >= 10) {
                                dp[i] += dp[i-2];
                        }
                }
                //5.返回值
                return dp[n-1];

        }

        public int numDecoding2(String s) {
                int n = s.length();
                char[] str = s.toCharArray();
                //1.状态表示
                int[] dp = new int[n+1];
                //2.优化后
                dp[0] = 1;
                if(str[1-1] != '0' ) {
                        dp[1] = 1;
                }
                //3.状态转移方程
                //4.填表顺序
                for(int i = 2; i <= n; i++) {
                        //i位置单独编码
                        if(str[i-1] != '0') {
                                dp[i] += dp[i-1];
                        }
                        //i-1与i一起编码
                        int t1 = 10 * (str[i-2]-'0') + (str[i-1]-'0');
                        if(t1 <= 26 && t1 >= 10) {
                                dp[i] += dp[i-2];
                        }
                }
                //5.返回值
                return dp[n];

        }
}
